【题解】 [ZJOI2010]基站选址 线段树优化DP luoguP2065 | Qiuly's blog!

【题解】 [ZJOI2010]基站选址 线段树优化DP luoguP2065

Posted on | In | Comments:

这题居然只有 $luogu$ 有……无法水多倍经验了（逃。

朴素的 $\rm{DP}$ 很简单，设 $f_{i,j}$ 表示前 $i$ 个村庄建了 $j$ 个基站的花费最小值，注意因为是前 $i$ 个，所有完全无视掉后面的所有村庄了。转移的话直接枚举一个 $k$ ，从 $f_{k,j-1}$ 转移过来即可，加上的代价就是中间村庄产生的补偿费用。

那么这样的复杂度就是 $O(n^2k)$ [爆炸] ，我们需要做到的就是如何快速计算中间村庄的补偿，那么外围的 $\rm{DP}$ 复杂度其实是 $O(nk)$ 的，如果中间的补偿可以快速算出那么就可以过掉了。

我们对于每一个村庄 $i$ ，用二分计算出最左边可以覆盖到其的村庄 $st_i$ 和最右边可以覆盖到其的村庄 $ed_i$ ，那么我们从 $i$ 到 $i+1$ 的时候，所有 $ed$ 值为 $i$ 的点都将失去右边的依靠，这个时候对于 $i+1$ 的最优转移点 $k$ ，有对于一个失去”右边依靠”的村庄 $j$ ，如果 $k$ 的范围在 $[1,st_j-1]$ 之间的话那么就要给 $j$ 补偿了。

于是我们考虑用线段树优化，对于这样一个村庄 $j$ ，我们在 $[1,st_j-1]$ 区间集体加上 $w_j$ ，表示决策点如果落在那个区间就要多付出 $w_j$ 的费用。

线段树的每个位置维护的就是 $f_k+$ $i$ 和 $k$ 中间村庄的补偿费用，因为我们每一次的答案就是整个区间的 $\min$ 值了，只是随着 $i$ 的变化线段树维护的值也应当做出变化，所以就会向上面那样更新。

不过有个问题，有个情况没有考虑道：第 $n$ 个村庄不建基站的情况，对于一个小于 $n$ 的 $i$ ，$f_i$ 管不了 $n$ ，那么 $f_n$ 也仅仅表示 $n$ 建站的情况。

所以我们需要在 $n+1$ 的位置上建一个辅助基站，当然 $c_{n+1}=0$ ，这样子就很好计算 第 $n$ 个村庄不建站时全局的花费了 。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=2e4+2;
const int K=1e2+2;
const int inf=1e9+9;

int head[N],cnt;
struct link{int nxt,to;} G[N<<2];
void add(int u,int v) {G[++cnt]=(link){head[u],v};head[u]=cnt;}

int n,k,d[N],c[N],s[N],w[N],f[N],st[N],ed[N];

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

namespace Segment_Tree {
    #define mid ((l+r)>>1)
    #define ls(x) ((x)<<1)
    #define rs(x) ((x)<<1|1)
    int val[N<<2],tag[N<<2];
    void pushdown(int x,int l,int r) {
        val[ls(x)]+=tag[x],tag[ls(x)]+=tag[x];
        val[rs(x)]+=tag[x],tag[rs(x)]+=tag[x];
        tag[x]=0;
    }
    void build(int x,int l,int r) {
        tag[x]=0;
        if(l==r) {val[x]=f[l];return;}
        build(ls(x),l,mid),build(rs(x),mid+1,r);
        val[x]=min(val[ls(x)],val[rs(x)]);
    }
    void change(int x,int l,int r,int L,int R,int v) {
        if(L==l&&r==R) {val[x]+=v,tag[x]+=v;return;}
        if(tag[x]) pushdown(x,l,r);
        if(R<=mid) change(ls(x),l,mid,L,R,v);
        else if(L>mid) change(rs(x),mid+1,r,L,R,v);
        else change(ls(x),l,mid,L,mid,v),change(rs(x),mid+1,r,mid+1,R,v);
        val[x]=min(val[ls(x)],val[rs(x)]);
    }
    int query(int x,int l,int r,int L,int R) {
        if(L==l&&r==R) return val[x];
        if(tag[x]) pushdown(x,l,r);
        if(R<=mid) return query(ls(x),l,mid,L,R);
        else if(L>mid) return query(rs(x),mid+1,r,L,R);
        else return min(query(ls(x),l,mid,L,mid),query(rs(x),mid+1,r,mid+1,R));
    }
}using namespace Segment_Tree;

int main() {
    IN(n),IN(k);
    for(int i=2;i<=n;++i) IN(d[i]);
    for(int i=1;i<=n;++i) IN(c[i]);
    for(int i=1;i<=n;++i) IN(s[i]);
    for(int i=1;i<=n;++i) IN(w[i]);
    ++n;w[n]=d[n]=inf;
    for(int i=1;i<=n;++i) {
        st[i]=lower_bound(d+1,d+1+n,d[i]-s[i])-d;
        ed[i]=lower_bound(d+1,d+1+n,d[i]+s[i])-d;
        if(d[ed[i]]>d[i]+s[i]) ed[i]--;add(ed[i],i);
    }
    int ans=inf;
    for(int i=1;i<=k;++i)
        if(i==1) {
            int res=0;
            for(int j=1;j<=n;++j) {
                f[j]=res+c[j];
                for(int e=head[j];e;e=G[e].nxt)
                    res+=w[G[e].to];
            }ans=f[n];
        } else {
            build(1,1,n);
            for(int j=1;j<=n;++j) {
                f[j]=(j>i-1?query(1,1,n,i-1,j-1):0)+c[j];
                for(int e=head[j],v;e;e=G[e].nxt)
                    if(st[v=G[e].to]>1) change(1,1,n,1,st[v]-1,w[v]); 
            }ans=min(ans,f[n]);
       }
    printf("%d\n",ans);
    return 0;
}

本文标题:【题解】 [ZJOI2010]基站选址 线段树优化DP luoguP2065

文章作者:Qiuly

发布时间:2019年05月09日 - 00:00

最后更新:2019年05月09日 - 22:43

原始链接:http://qiulyblog.github.io/2019/05/09/[题解]luoguP2605/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。